package l.l.w.practice.EightQueens;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by llw on 2017/9/4.
 *
 */
public class EightQueensRecurison {

    public int eightQueens(int num){
        List<List<Integer>> all = new LinkedList<>();
        int[] location = new int[num+1];
        int count=0;
        return eightQueensRecurison(0,num,all,location,count);
    }

    private int eightQueensRecurison(int i, int num, List<List<Integer>> all, int[] location,int count) {
        if(i>=num){
            count++;
//            List<Integer> list = new ArrayList<>(num);
//            for(int k=0;k<num;++k){
////                System.out.print(location[k]+" ");
////                list.add(k);
//            }
//            System.out.println();
//            all.add(list);
        }else{
            for(int j=0;j<num;++j){
                location[i]=j;
                if(check(location,i)){
                    count = eightQueensRecurison(i+1,num,all,location,count);
                }
            }
        }
        return count;
    }

    private boolean check(int[] location, int i) {
        for(int j=0;j<i;++j){
            if(Math.abs(i-j)==Math.abs(location[i]-location[j]) || location[i]==location[j]){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int num = 16;
        int count = new EightQueensRecurison().eightQueens(num);
        System.out.println(count);
    }
}
